Exchange of value range and definition range
When the value domain is narrow (narrowed by problem constraints) or the definition domain is excessively wide (such as the whole subset 2^2000), problem transformation to exchange the value domain and the definition domain is effective in some cases. Represent a set of values as an array where the subscripts are the values and 1 stands for 1.
When the value range is narrower than the definition range, instead of finding the largest value in the definition range, find the largest subscript in the value range that satisfies the constraint
gcd for a subset of a set of 2000 elements, the domain is 2^2000, but the value range is smaller with a set of 2000 divisors
---
This page is auto-translated from /nishio/値域と定義域の交換. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.